The present invention relates, in general, to a method and apparatus for locating and retrieving data from an index in a binary digital memory.
Data indexes are frequently employed in applications where specific data is to be located in, and retrieved from, a memory containing a large quantity of data, such as a database. Searching for specific data in a large database is usually a time consuming procedure, even though it is implemented on a computer.
A common problem in indexing systems is that the data is not identified in an efficient manner. For example, consider automobile part numbers. These numbers are often made up of perhaps a dozen or more digits and letters, and there are therefore trillions of possible part numbers. However, perhaps only fifty thousand of those numbers will be assigned to actual parts. To locate the parts in a warehouse or to locate the part inventory records stored in a file, an index is required to map the small subset of assigned part numbers to a set of location numbers. Clearly, it would be very inefficient and time consuming if the part number searching procedure implemented by the index involved searching all possible part numbers, whether the numbers have actually been assigned to parts or not.
Another example of this problem is a book index which maps words to page numbers. Since there are more than 200 billion (26.sup.8) possible combinations of eight letters, but a considerably smaller number of eight letter words, the same situation exists here as with the automobile parts, where a few elements from a large set are mapped onto a second smaller set.
This indexing problem can also be illustrated by the pattern recognition process employed by the human brain. There is an extremely large number of possible patterns of sensory inputs that can be presented to the millions of sensory neurons, but only a relatively small number of those patterns have "meaning" and will be recognized by the brain.
Computers have been utilized to implement data indexes because of their inherent capability of being able to search through a large quantity of data in a relatively short period of time. Sequential searching is the simplest approach, but is usually too slow. Various software techniques, such as hash codes, table look up algorithms, B-trees and other approaches have been developed in an effort to speed up the process.
Hash codes are often utilized to solve the problem discussed above, and are algorithms which transform a large number into a smaller one, usually through use of some type of division algorithm. All of these software techniques still require substantial time for the execution of the algorithms. The present invention seeks to overcome this drawback.